package com.dy.图.最小生成树;

import java.util.Arrays;
import java.util.Comparator;

//生成树中权重和最小的
class Edge  {
    public int i, j, w;

    public Edge(int i, int j, int w) {
        this.i = i;
        this.j = j;
        this.w = w;
    }
}
public class 最小生成树 {

    public static void prim(int[][] G,char v[],int start){
        int num = v.length;//顶点数量
        char[] prim = new char[num];//用于加入的点
        int index=0;
        //前驱节点
        int[] prenode = new int[num];
        int weight[] = new int[num];//记录从start点开始到其他个点的距离

        for(int i=0;i<num;i++){
            prenode[i] = start;
            weight[i] = G[start][i];
        }

        int sum=0;
        //weitght为0时表示加入该点
        weight[start] =0;

        prim[index++] = v[start];//将起始点加入

        //循环n-1次，每次找到距离start点最短的点
        for(int i=0;i<num-1;i++){
            //
            //if(i==start) continue;

            int j=0;
            int min = Integer.MAX_VALUE;

            int k=0;
            //遍历所有点，找到最短距离的顶点
            while(j<num){
                if(weight[j]!=0 &&weight[j]<min){
                    min = weight[j];
                    k=j;
                }
                j++;
            }
            prim[index++] = v[k];
            System.out.println("访问到了边{"+prenode[k]+","+k+"},权重为"+min);
//            System.out.println("前驱是"+prenode[k]);
//            System.out.println("找到点:"+k);
            sum +=min;
            weight[k]=0;
            //更新边距
            for(int m=0;m<num;m++){
                if(weight[m]!=0&&weight[m]>G[k][m]){
                    prenode[m] = k;
                    weight[m]=G[k][m];
                }
            }
        }
        System.out.println("最小权值和是："+sum);



    }
    /**
     * 克鲁斯卡尔算法
     * 将图的边权值按从小到大排序，选取的边未构成回路，则加入边集，直到边集有了n-1条边为止


     1
     /  |  \
     2 ——  3 —— 4
     \  / \  /
     5 —— 6


     */
    public static void KRUSKAL(int [] V,Edge [] E){
        Arrays.sort(E, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.w-o2.w;
            }
        });
        // 定义一个一维数组，下标为连线的起点，值为连线的终点
        int[] parent = new int[E.length];

        int sum = 0;
        for(Edge e:E){
            int start = find(parent,e.i);
            int end = find(parent,e.j);
            if(start!=end){
                parent[start] =end;
                System.out.println("访问到了边{"+start+","+end+"},权重为"+e.w);
                sum+=e.w;
            }
        }
        System.out.println("总权值="+sum);
    }

    private  static int find(int parent[],int index){
        while(parent[index]>0){
            index = parent[index];
        }
        return index;
    }
    public final static int INF=Integer.MAX_VALUE;
    public static void main(String[] args) {
        int [] V={1,2,3,4,5,6};//顶点
        Edge [] E=new Edge[10];
        E[0]=new Edge(1,2,6);
        E[1]=new Edge(1,3,1);
        E[2]=new Edge(1,4,5);
        E[3]=new Edge(2,3,5);
        E[4]=new Edge(2,5,3);
        E[5]=new Edge(3,4,5);
        E[6]=new Edge(3,5,6);
        E[7]=new Edge(3,6,4);
        E[8]=new Edge(4,6,2);
        E[9]=new Edge(5,6,6);
        //KRUSKAL(V,E);

        char[] v={'0','1','2','3','4','5'};
        int[][] G={
                {INF,7,1,5,INF,INF},
                {7,INF,6,INF,3,INF},
                {1,6,INF,7,6,4},
                {5,INF,7,INF,INF,},
                {INF,3,6,INF,INF,7},
                {INF,INF,4,2,7,INF}
        };
        prim(G,v,0);
    }


}
